#include <iostream>
#include <vector>
using namespace std;

class Solution {
	bool can(vector<int> &t, int limit, int status, int cur, int len, vector<int> &dp)
	{
		if (cur == 4) {
			return true;
		}

		if (dp[status] != -1) {
			return dp[status];
		}

		for (int i = 0; i < t.size(); i++) {
			if (status & (1 << i)) {
				if (len + t[i] < limit && can(t, limit, status ^ (1 << i), cur, len + t[i], dp)) {
					return dp[status] = true;
				}
				if (len + t[i] == limit && can(t, limit, status ^ (1 << i), cur + 1, 0, dp)) {
					return dp[status] = true;
				}
			}
		}
		return dp[status] = false;
	}

    public:
	bool makesquare(vector<int> &matchsticks)
	{
		int sum = 0;
		for (auto v : matchsticks) {
			sum += v;
		}
		if (sum % 4) {
			return false;
		}

		int limit = sum / 4;
		int n = matchsticks.size();
		int status = (1 << n) - 1;
		vector<int> dp(status + 1, -1);
		return can(matchsticks, limit, status, 0, 0, dp);
	}
};

int main()
{
	vector<int> matchsticks = { 3,3,3,3,4 };
	cout << Solution().makesquare(matchsticks) << endl;
	return 0;
}